/**
 *  @file FourFundamentalOperate.c
 *  @brief 基于栈实现的四则运算表达式求值程序
 *  @details 实现支持 +, -, *, / 运算符及括号的中缀表达式计算，
 *           利用两个栈（操作数栈与操作符栈）完成表达式求值。
 *  @author WangBlue (wangjiping596@gmail.com)
 *  @date 2025-07-30 14:53
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <ctype.h>
#define MAX_SIZE 100

/**
 * @brief 整数栈结构体
 */
typedef struct stack {
    int data[MAX_SIZE];  ///< 栈中存储的数据
    int top;             ///< 栈顶索引，-1 表示空栈
} stack;

/**
 * @brief 字符栈结构体（用于存储运算符）
 */
typedef struct charStack {
    char data[MAX_SIZE]; ///< 栈中存储的字符数据（运算符）
    int top;             ///< 栈顶索引，-1 表示空栈
} charStack;

/**
 * @brief 初始化整数栈
 * @param s 指向整数栈的指针
 */
void initStack(stack *s) {
    s->top = -1;
    for (int i = 0; i < MAX_SIZE; i++) {
        s->data[i] = 0;
    }
}

/**
 * @brief 初始化字符栈
 * @param s 指向字符栈的指针
 */
void initCharStack(charStack *s) {
    s->top = -1;
    for (int i = 0; i < MAX_SIZE; i++) {
        s->data[i] = 0;
    }
}

/**
 * @brief 判断整数栈是否为空
 * @param s 指向整数栈的指针
 * @return true为空，false非空
 */
bool isEmpty(stack *s) {
    return s->top == -1;
}

/**
 * @brief 判断字符栈是否为空
 * @param s 指向字符栈的指针
 * @return true为空，false非空
 */
bool isCharStackEmpty(charStack *s) {
    return s->top == -1;
}

/**
 * @brief 判断整数栈是否已满
 * @param s 指向整数栈的指针
 * @return true为满，false未满
 */
bool isFill(stack *s) {
    return s->top == MAX_SIZE - 1;
}

/**
 * @brief 判断字符栈是否已满
 * @param s 指向字符栈的指针
 * @return true为满，false未满
 */
bool isCharStackFill(charStack *s) {
    return s->top == MAX_SIZE - 1;
}

/**
 * @brief 整数栈压栈操作
 * @param s 指向整数栈的指针
 * @param value 待压入的整数值
 */
void push(stack *s, int value) {
    if (isFill(s)) return;
    s->top++;
    s->data[s->top] = value;
}

/**
 * @brief 字符栈压栈操作
 * @param s 指向字符栈的指针
 * @param value 待压入的字符值（运算符）
 */
void pushCharStack(charStack *s, char value) {
    if (isCharStackFill(s)) return;
    s->top++;
    s->data[s->top] = value;
}

/**
 * @brief 整数栈弹栈操作
 * @param s 指向整数栈的指针
 * @param value 指针，用于存储弹出的栈顶元素
 */
void pop(stack *s, int *value) {
    if (isEmpty(s)) return;
    *value = s->data[s->top];
    s->top--;
}

/**
 * @brief 字符栈弹栈操作
 * @param s 指向字符栈的指针
 * @param value 指针，用于存储弹出的栈顶字符
 */
void popCharStack(charStack *s, char *value) {
    if (isCharStackEmpty(s)) return;
    *value = s->data[s->top];
    s->top--;
}

/**
 * @brief 获取整数栈栈顶元素（不弹出）
 * @param s 指向整数栈的指针
 * @return 栈顶元素，空栈返回-1
 */
int peek(stack *s) {
    if (isEmpty(s)) return -1;
    return s->data[s->top];
}

/**
 * @brief 获取字符栈栈顶元素（不弹出）
 * @param s 指向字符栈的指针
 * @return 栈顶字符，空栈返回 '\0'
 */
char peekCharStack(charStack *s) {
    if (isCharStackEmpty(s)) return '\0';
    return s->data[s->top];
}

/**
 * @brief 打印整数栈中所有元素（从底到顶）
 * @param s 指向整数栈的指针
 */
void printStack(stack *s) {
    if (isEmpty(s)) return;
    for (int i = 0; i <= s->top; i++) {
        printf("value is %d\n", s->data[i]);
    }
    printf("\n");
}

/**
 * @brief 获取运算符优先级
 * @param op 运算符字符 '+', '-', '*', '/'
 * @return 优先级整数值，乘除为1，加减为0，非法运算符返回-1
 */
int precedence(char op) {
    if (op == '*' || op == '/') return 1;
    if (op == '+' || op == '-') return 0;
    return -1;
}

/**
 * @brief 计算两个操作数和运算符的结果
 * @param a 操作数1（左操作数）
 * @param b 操作数2（右操作数）
 * @param op 运算符字符
 * @return 计算结果
 * @note 除法时若除数为0，程序会打印错误并退出
 */
int calc(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/':
            if (b == 0) {
                printf("the divisor cannot be 0\n");
                exit(EXIT_FAILURE);
            }
            return a / b;
        default:
            printf("Error: unsupported operator '%c'\n", op);
            exit(EXIT_FAILURE);
    }
}

/**
 * @brief 判断括号是否为匹配的一对
 *
 * 支持三种括号类型：小括号 ()，中括号 []，大括号 {}
 *
 * @param open 左括号字符
 * @param close 右括号字符
 * @return true 如果 open 和 close 组成合法的一对括号
 * @return false 否则（不匹配或不是括号）
 */
bool isMatchingPair(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '[' && close == ']') ||
           (open == '{' && close == '}');
}

/**
 * @brief 计算给定中缀表达式的值
 * @param expr 中缀表达式字符串，支持空格、整数、多位数、括号和四则运算符
 * @return 计算结果整数
 * @note 如果表达式非法，程序会打印错误信息并退出
 */
int evaluate(char *expr) {
    charStack operate;   // 运算符栈
    initCharStack(&operate);

    stack numbers;       // 操作数栈
    initStack(&numbers);

    for (int i = 0; expr[i]; i++) {
        if (isspace(expr[i])) continue;  // 跳过空白字符

        if (isdigit(expr[i])) {
            int num = 0;
            while (isdigit(expr[i])) {
                num = num * 10 + (expr[i] - '0');
                i++;
            }
            i--; // 回退多读的一位
            push(&numbers, num);
        } else if (expr[i] == '(' || expr[i] == '[' || expr[i] == '{') {
            pushCharStack(&operate, expr[i]);
        } else if (expr[i] == ')' || expr[i] == ']' || expr[i] == '}') {
            while (!isCharStackEmpty(&operate) &&
                   !isMatchingPair(peekCharStack(&operate), expr[i])) {

                char topOp = peekCharStack(&operate);
                if (topOp == '(' || topOp == '[' || topOp == '{') {
                    printf("Error: mismatched parentheses\n");
                    exit(EXIT_FAILURE);
                }

                int a, b;
                char op;
                pop(&numbers, &a);
                pop(&numbers, &b);
                popCharStack(&operate, &op);
                int result = calc(b, a, op);
                push(&numbers, result);
            }

            if (isCharStackEmpty(&operate)) {
                printf("Error: mismatched parentheses\n");
                exit(EXIT_FAILURE);
            }

            char discard;
            popCharStack(&operate, &discard); // 弹出左括号，不参与计算
        } else if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/') {
            while (!isCharStackEmpty(&operate) &&
                precedence(peekCharStack(&operate)) >= precedence(expr[i]) ) {
                int a, b;
                char op;
                pop(&numbers, &a);
                pop(&numbers, &b);
                popCharStack(&operate, &op);
                int result = calc(b, a, op);
                push(&numbers, result);
            }
            pushCharStack(&operate, expr[i]);
        } else {
            printf("Error: unsupported character '%c'\n", expr[i]);
            exit(EXIT_FAILURE);
        }
    }

    while (!isCharStackEmpty(&operate)) {
        char op = peekCharStack(&operate);
        if (op == '(' || op == '[' || op == '{') {
            printf("Error: mismatched parentheses\n");
            exit(EXIT_FAILURE);
        }

        int a, b;
        pop(&numbers, &a);
        pop(&numbers, &b);
        popCharStack(&operate, &op);
        int result = calc(b, a, op);
        push(&numbers, result);
    }

    int finalResult;
    pop(&numbers, &finalResult);
    return finalResult;
}

/**
 * @brief 主函数，包含若干测试用例验证表达式计算正确性（含 ()、[]、{} 三种括号）
 */
int main() {
    const char *tests[] = {
        "3 + 5 * 2",
        "(10 + 2) * 3",
        "100 / (5 * (2 + 3))",
        "((2+3)*4 - 6) / 2",
        "1 + 2 - 3 * 4 / 2 + (6 - 1)",
        "7 + 3 * (10 / (12 / (3 + 1) - 1))",
        "42",
        "8 * 3 + 12 / 4",
        "(((((1+1)))))",
        "0 + 0 * (0 + 0)",
        "5 + 15 / 3 * 2 - 4",
        "(8 + 2) * (9 - 6) / 3",
        "10 / 2 * 3 + 1",
        "100 / 10 / 2",
        "9 - 3 + 1",
        "[(2+3)*4 - {6/2}]",                       // 中括号+大括号混用
        "{[1+2]*3} + (4*5)",                       // 三种括号嵌套
        "10 + {2 * [3 + (4 - 1)]}"                 // 更复杂的混合嵌套
    };

    int expected_results[] = {
        13,   // 3 + 5 * 2
        36,   // (10 + 2) * 3
        4,    // 100 / (5 * (2 + 3))
        7,    // ((2+3)*4 - 6) / 2
        2,    // 1 + 2 - 3 * 4 / 2 + (6 - 1)
        22,   // 7 + 3 * (10 / (12 / (3 + 1) - 1))
        42,   // 42
        27,   // 8 * 3 + 12 / 4
        2,    // (((((1+1)))))
        0,    // 0 + 0 * (0 + 0)
        11,   // 5 + 15 / 3 * 2 - 4
        10,   // (8 + 2) * (9 - 6) / 3
        16,   // 10 / 2 * 3 + 1
        5,    // 100 / 10 / 2
        7,    // 9 - 3 + 1
        17,   // [(2+3)*4 - {6/2}]  → (2+3)*4 = 20, {6/2}=3, 20-3=17
        29,   // {[1+2]*3} + (4*5) → [1+2]=3,*3=9, (4*5)=20, 9+20=29
        22    // 10 + {2 * [3 + (4 - 1)]} → (4-1)=3,+3=6,[…]=6,2*6=12,10+12=22
    };

    int n_tests = sizeof(tests) / sizeof(tests[0]);

    for (int i = 0; i < n_tests; i++) {
        int result = evaluate1((char *)tests[i]);
        printf("Test %2d: %-40s Expected: %3d, Got: %3d %s\n",
               i + 1, tests[i], expected_results[i], result,
               (result == expected_results[i]) ? "yes" : "no");
    }

    return 0;
}
